package com.leetcode.algorithm.y22.m06;

/**
 * 918. 环形子数组的最大和
 * 
 * https://leetcode.cn/problems/maximum-sum-circular-subarray/
 * 
 * @author jie.deng
 *
 */
class Question0918Solution01 {

	public int maxSubarraySumCircular(int[] nums) {
		int len = nums.length;

		// 第一步：求nums[j...i]子数组的最大和
		// DP状态定义
		// dp[i]表示 nums[j...i](j>=0)子数组的最大可能和
		int[] dp = new int[len];
		dp[0] = nums[0];
		for (int i = 1; i < len; i++) {
			dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
		}
		int maxSum = dp[0];
		for (int i = 1; i < len; i++) {
			maxSum = Math.max(maxSum, dp[i]);
		}

		// 第二步：求nums[j...i]子数组的最小和
		// dp[i]表示 nums[j...i](j>=0)子数组的最小可能和
		dp[0] = nums[0];
		for (int i = 1; i < len; i++) {
			dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]);
		}
		// 可以一个元素都没有，即最小为0; 但是也不能包含所有元素
		int minSum = 0;
		for (int i = 0; i < len; i++) {
			minSum = Math.min(minSum, dp[i]);
		}

		// 第三步：求nums[0...len]的和
		int sum = 0;
		for (int i = 0; i < len; i++) {
			sum += nums[i];
		}

		return Math.max(maxSum, sum < 0 && sum == minSum ? sum : sum - minSum);
	}

}